from collections import defaultdict
from itertools import chain
from typing import List

class Node:
    def __init__(self):
        self.label = None
        self.adj = defaultdict(Node)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        root = Node()
        root.label = ' '
        for word in wordDict:
            node = root
            for c in word:
                node = node.adj[c]
                node.label = c
            node.adj[' '] = root

        paths = [[root]]
        for c in s:
            eps_paths = []
            for path in paths:
                if ' ' in path[-1].adj:
                    new_path = path + [root]
                    eps_paths.append(new_path)
            new_paths = []
            for path in chain(paths, eps_paths):
                if c in path[-1].adj:
                    new_path = path + [path[-1].adj[c]]
                    new_paths.append(new_path)
            paths = new_paths
        eps_paths = []
        for path in paths:
            if ' ' in path[-1].adj:
                new_path = path + [root]
                eps_paths.append(new_path)
        result = []
        for path in eps_paths:
            labels = []
            for node in path:
                labels.append(node.label)
            sentence = ''.join(labels).strip()
            result.append(sentence)
        return result


s = "catsanddog"
wordDict = ["cat","cats","and","sand","dog"]
print(Solution().wordBreak(s, wordDict))

